[UVA 1347] Tour

原题链接:[UVA 1347] Tour

原题大意:一个图上有nn个点,给定他们的坐标.现在分别有两个人在最左端和最右端的点上移动,各个点的xx坐标都是不同的.两个人不能走到同一个点上,问走过的总距离最少是多少.
数据范围:
1n10001 \leq n \leq 1000

思路

显然让两个人从左边走到右边,又从右边走到左边是非常蛋疼的.不过由于距离是欧式距离是双向的,不妨把这个问题变成两个人同时从起点出发,且经过的点不重复的最小距离.这就很像一个网络流的模型,但是费用流做不了,或者说很难做,首先必须保证所有的点都经过了,其次边可能达到10610^6的级别,这是跑不了的.
现在来考虑DP,一个比较直接的想法就是f[i][j]f[i][j]表示第一个人走到了ii,第二个人走到了jj.入口出口都比较好想,但是没法转移:因为这个状态根本没有一个是否能走到下一个点的信息,假如现在要计算f[i][j]f[i][j]i+1i+1这个点是否被用过了,根本不知道,没法转移.
既然如此,就把状态修改成这样:f[i][j]f[i][j]表示1 max(i,j)1~max(i,j)这些点都被经过了的前提下,两者位置分别是i,ji,j,剩余还要走的最小距离是多少.这个状态就可以解决掉之前的问题,即可以知道一个信息:i+1i+1这个点有没有被用过.在此基础上,减少一定的讨论,可以规定i>ji>j,这样就可以在不影响答案的前提下去减少一些讨论.不过这样还是不能转移,因为当前是f[i][j]f[i][j]的时候,如果直接走到i+2i+2这个点,显然i+1i+1这个点就走不了了,因为状态根本没法表示了,但是这个转移的时候又没有限制,这里有个很巧妙的想法:禁止这样的转移,每次转移就只能走到i+1i+1.为什么这样是正确的呢,因为当走到i+2i+2的时候,其实第二个人必须要走过i+1i+1这个点,不妨就让第二个人先转移到i+1i+1再让第一个人走到i+2i+2上,这个结果上是符合要求的,也不会出现一个点没有被用到的情况.
重新梳理一下过程:
状态:f[i][j]f[i][j]表示当前已经走过了1i1-i这些点,并且i>ji>j.两者分别在i,ji,j这两点上时,剩余还要走的距离的所有集合里最小的具体值是多少.
入口:f[n][n1]=dist(n,n1)f[n][n - 1] = dist(n,n-1)
转移:转移有两种,一种是从ii走到i+1i+1.这种情况下就是f[i+1][j]+dist(i,i+1)f[i + 1][j] + dist(i,i+1).另一种是第二个人走到i+1i+1,即f[i+1][i]+dist(i+1,j)f[i + 1][i] + dist(i + 1,j)注意这里本来是f[i][i+1]f[i][i + 1]的,但是之前定义的时候要求保证i>ji>j所以调换了顺序.
出口:答案就是dist(1,2)+f[2][1]dist(1,2) + f[2][1]

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n;
double x[N],y[N],f[N][N];
double gdist(int a,int b)
{
	double dx = x[a] - x[b],dy = y[a] - y[b];
	return sqrt(dx * dx + dy * dy);
}
int main()
{
	while((scanf("%d",&n)) == 1)
	{
		for(int i = 1;i <= n;++i)	scanf("%lf%lf",&x[i],&y[i]);
		for(int i = 1;i <= n;++i)	for(int j = 1;j <= n;++j)	f[i][j] = 1e10;
		f[n][n - 1] = gdist(n,n - 1);		
		for(int i = n - 1;i >= 1;--i)
		{
			for(int j = i - 1;j >= 1;--j)
			{
				auto& v = f[i][j];
				v = min(v,f[i + 1][j] + gdist(i,i + 1));
				v = min(v,f[i + 1][i] + gdist(j,i + 1));
			}
		}
		// cout << f[2][1] << endl;
		printf("%.2lf\n",f[2][1] + gdist(1,2));
	}	
    return 0;
}